package algorithms.leaning.class19;

import common.util.MyUtil;

/**
 * 给定两个长度都为N的数组weights和values，
 * weights[i]和values[i]分别代表 i号物品的重量和价值。
 * 给定一个正数bag，表示一个载重bag的袋子，
 * 你装的物品不能超过这个重量。
 * 返回你能装下最多的价值是多少?
 *
 * @author guichang
 * @date 2021/6/18
 */

@SuppressWarnings("all")
public class Code1_动态规划_背包问题 {

    public static void main(String[] args) {
        int bag = 3;
        int[] ws = MyUtil.createArray(1, 2, 3, 0, 0, 1);
        int[] vs = MyUtil.createArray(5, 11, 15, 1, 1, 6);
        MyUtil.print(maxValue(ws, vs, bag));
        MyUtil.print(maxValueDp(ws, vs, bag));
    }

    public static int maxValue(int[] ws, int[] vs, int bag) {
        // 边界
        if (ws == null || vs == null || ws.length == 0 || ws.length != vs.length) {
            return -1;
        }
        return process(ws, vs, 0, bag);
    }

    /**
     * 来到curr位置的时候的最大价值
     *
     * @param ws   重量数组
     * @param vs   价值数组
     * @param index 当前位置
     * @param rest 剩下的重量
     * @return 最大价值
     */
    private static int process(int[] ws, int[] vs, int index, int rest) {
        // base case
        if (index >= ws.length) {
            return 0;
        }
        // 要当前的前提是剩余的足够
        int currYes = Integer.MIN_VALUE;
        if (rest >= ws[index]) {
            currYes = vs[index] + process(ws, vs, index + 1, rest - ws[index]);
        }
        // 不要当前的
        int currNo = process(ws, vs, index + 1, rest);
        // 取最大值
        return Math.max(currYes, currNo);
    }

    /**
     * 严格位置依赖版本
     */
    public static int maxValueDp(int[] ws, int[] vs, int bag) {
        // 边界
        if (ws == null || vs == null || ws.length == 0 || ws.length != vs.length) {
            return -1;
        }
        int N = ws.length;
        int[][] dp = new int[N + 1][bag + 1];
        // 可忽略dp[N][……] = 0
        // 整体从下往上，内部从左往右
        for (int index = N - 1; index >= 0; index--) {
            for (int rest = 0; rest <= bag; rest++) {
                // 要当前的前提是剩余的足够
                int currYes = rest >= ws[index] ? vs[index] + dp[index + 1][rest - ws[index]] : Integer.MIN_VALUE;
                // 不要当前的
                int currNo = dp[index + 1][rest];
                // 取最大值
                dp[index][rest] = Math.max(currYes, currNo);
            }
        }
        return dp[0][bag];
    }


}